4 keys keyboard

Time: O(1); Space: O(1); medium

Imagine you have a special keyboard with the following keys:

  • Key 1: (A): Print one ‘A’ on screen.

  • Key 2: (Ctrl-A): Select the whole screen.

  • Key 3: (Ctrl-C): Copy selection to buffer.

  • Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for N times (with the above four keys),

find out the maximum numbers of ‘A’ you can print on screen.

Example 1:

Input: 3

Output: 3

Explanation:

  • We can at most get 3 A’s on screen by pressing following key sequence: A, A, A

Example 2:

Input: 7

Output: 9

Explanation:

  • We can at most get 9 A’s on screen by pressing following key sequence: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Constraints:

  • 1 <= N <= 50

  • Answers will be in the range of 32-bit signed integer.

Explanation:

  • We either press ‘A’, or press ‘CTRL+A’, ‘CTRL+C’, and some number of ’CTRL+V’s.

  • Thus, in the context of making N keypresses to write the letter ‘A’ M times, there are only two types of moves:

    • Add (1 keypress): Add 1 to M.

    • Multiply (k+1 keypresses): Multiply M by k, where k >= 2.

  • In the following explanations, we will reference these as moves.

[2]:

class Solution1(object):
    """
    Time: O(1)
    Space: O(1)
    """
    def maxA(self, N) -> int:
        """
        :type N: int
        :rtype: int
        """
        if N < 7:
            return N
        if N == 10:
            return 20  # the following rule doesn't hold when N = 10

        n  = N // 5 + 1  # n3 + n4 increases one every 5 keys
        # (1) n     =     n3 +     n4
        # (2) N + 1 = 4 * n3 + 5 * n4
        #     5 x (1) - (2) => 5*n - N - 1 = n3
        n3 = 5 * n - N - 1
        n4 = n - n3
        return 3**n3 * 4**n4

[3]:

s = Solution1()
N = 3
assert s.maxA(N) == 3
N = 7
assert s.maxA(N) == 9

[5]:

class Solution2(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def maxA(self, N) -> int:
        """
        :type N: int
        :rtype: int
        """
        if N < 7:
            return N
        dp = [x for x in range(N + 1)]
        for i in range(7, N + 1):
            dp[i % 6] = max(dp[(i-4) % 6] * 3, dp[(i-5) % 6] * 4)
        return dp[N % 6]

[6]:

s = Solution2()
N = 3
assert s.maxA(N) == 3
N = 7
assert s.maxA(N) == 9